from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def productExceptSelf(self, nums):
        n = len(nums)
        pre_nums=[0]*n
        tail_nums = [0]*n
        result =[0] * n
        # 前缀积
        pre_nums[0] = nums[0]
        for i in range(1,n):
            pre_nums[i]=pre_nums[i-1]*nums[i]
        # 后缀积
        tail_nums[n-1] = nums[n-1]
        for i in range(n-2,-1,-1):
            tail_nums[i]=tail_nums[i+1]*nums[i]
        result[0] = tail_nums[1]
        result[n-1] = pre_nums[n-2]
        for i in range(1,n-1):
            result[i] = pre_nums[i-1]*tail_nums[i+1]
        return result
        
# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    solution.productExceptSelf([1,2,3,4])
    # your test code here